package com.cango.student.algorithm.leetcode;

import com.cango.student.algorithm.nodepackage.Node;

/**
 * 两两交换链表中的节点
 * swap-nodes-in-pairs
 */
public class swapPairs {
    public Node swapPairs(Node head) {
        Node root = new Node(0);//必须定义一个根节点，从而记住最后链表的头部
        root.next = head;//自定义节点next与链表链接上
        Node pre = root;//需要一个节点记住，发生交换前，上一次交换的末尾节点索引点

        while (pre.next != null && pre.next.next != null) {//下一次交换的下一个节点，下下个节点都不为空才能交换
            Node start = pre.next;//定义下一次交换的第一个节点
            Node then = start.next;//定义下一次交换的第二个节点
            //第一个和第二个节点位置交换
            //这里有个必须注意的是，链表位置交换，比如1->2->3->4->5，这个链表，2和3要交换。执行交换操作就是
            //1先指向3，然后2执行4，最后3指向2,这样就链接起来了。
            pre.next = then;
            start.next = then.next;
            then.next = start;

            pre = start;//最后更新下一次交换前的上个节点node
        }
        return root.next;
    }

    public static void main(String[] args) {
        swapPairs swapPairs = new swapPairs();

        Node one = new Node(1);
        Node tw0 = new Node(2);
        Node three = new Node(3);
        Node four = new Node(4);

        one.next=tw0;
        tw0.next=three;
        three.next = four;
        swapPairs.swapPairs(one);
    }
}
